;/*template <class T>
class UnionFindSet
{
public:
	UnionFindSet(int size)
		:_ufs(size, -1)
	{}

	size_t FindRoot(int x)
	{
		while (_ufs[x] >= 0)
		{
			x = _ufs[x];
		}
		return x;
	}

	void Union(int x, int y)
	{
		size_t root1 = FindRoot(x);
		size_t root2 = FindRoot(y);
		if (root1 != root2)
		{
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
		}
	}

	size_t SetCount()
	{
		int count = 0;
		for (size_t i = 0; i < _ufs.size(); i++)
		{
			if (_ufs[i] < 0)
				count++;
		}
		return count;
	}
private:
	std::vector<T> _ufs;
};

class Solution {
public:
	int findCircleNum(vector<vector<int>>& isConnected) {
		UnionFindSet<int> ufs(isConnected.size());
		for (int i = 0; i < isConnected.size(); i++)
		{
			for (int j = 0; j < isConnected[i].size(); j++)
			{
				if (isConnected[i][j] == 1)
					ufs.Union(i, j);
			}
		}
		return ufs.SetCount();
	}
};*/


//class Solution {
//public:
//	int findCircleNum(vector<vector<int>>& isConnected) {
//		vector<int> ufs(isConnected.size(), -1);
//		auto FindRoot = [&ufs](int x) {
//			while (ufs[x] >= 0)
//			{
//				x = ufs[x];
//			}
//			return x;
//		};
//
//		for (int i = 0; i < isConnected.size(); i++)
//		{
//			for (int j = 0; j < isConnected[i].size(); j++)
//			{
//				if (isConnected[i][j] == 1)
//				{
//					int root1 = FindRoot(i);
//					int root2 = FindRoot(j);
//					if (root1 != root2)
//					{
//						ufs[root1] += ufs[root2];
//						ufs[root2] = root1;
//					}
//				}
//			}
//		}
//
//		int ret = 0;
//		for (int i = 0; i < ufs.size(); i++)
//		{
//			if (ufs[i] < 0) ret++;
//		}
//		return ret;
//	}
//};



class Solution {
public:
	bool equationsPossible(vector<string>& equations) {
		vector<int> ufs(26, -1);
		auto findRoot = [&ufs](int x)
		{
			while (ufs[x] >= 0)
				x = ufs[x];

			return x;
		};

		for (auto& str : equations)
		{
			if (str[1] == '=')
			{
				int root1 = findRoot(str[0] - 'a');
				int root2 = findRoot(str[3] - 'a');
				if (root1 != root2)
				{
					ufs[root1] += ufs[root2];
					ufs[root2] = root1;
				}
			}
		}

		for (auto& str : equations)
		{
			if (str[1] == '!')
			{
				int root1 = findRoot(str[0] - 'a');
				int root2 = findRoot(str[3] - 'a');
				if (root1 == root2)
				{
					return false;
				}
			}
		}
		return true;
	}
};